/*
 * @lc app=leetcode.cn id=220 lang=typescript
 *
 * [220] 存在重复元素 III
 */

// @lc code=start
function containsNearbyAlmostDuplicate(nums: number[], k: number, t: number): boolean {
  const bucket: Map<number, number> = new Map();

  const getBucketId = (x: number, size: number): number => {
    return x < 0 ? Math.ceil(x / size) - 1 : Math.floor(x / size);
  };

  for (let i = 0; i < nums.length; i++) {
    const x = nums[i];
    const id = getBucketId(x, t + 1);

    if (bucket.has(id)) {
      return true;
    }
    if (bucket.has(id - 1) && Math.abs(nums[i] - bucket.get(id - 1)) <= t) {
      return true;
    }
    if (bucket.has(id + 1) && Math.abs(nums[i] - bucket.get(id + 1)) <= t) {
      return true;
    }
    bucket.set(id, x);
    // 维护窗口大小
    if (i >= k) {
      bucket.delete(getBucketId(nums[i - k], t + 1));
    }
  }

  return false;
}
// @lc code=end
